package top.interview

import problem.Problem

import scala.annotation.tailrec

class Q88MergeSortedArray extends Problem {

  def merge(nums1: Array[Int], m: Int, nums2: Array[Int], n: Int): Unit = {
    merge(nums1, m - 1, m + n - 1, nums2, n - 1)
  }

  @tailrec
  final def merge(a: Array[Int], i: Int, f: Int, b: Array[Int], j: Int): Unit = {
    if (i < 0) (0 to j).foreach(c => a(f - c) = b(j - c))
    else if (j < 0) Unit
    else {
      val (fv, ni, nj) =
        if (a(i) <= b(j)) (b(j), i, j - 1)
        else (a(i), i - 1, j)
      a(f) = fv
      merge(a, ni, f - 1, b, nj)
    }
  }

  override def test(): Unit = {
    val a1 = Array(1, 2, 3, 0, 0, 0)
    val b1 = Array(2, 5, 6)
    merge(a1, 3, b1, 3)
    a1 shouldBe Array(1, 2, 2, 3, 5, 6)
  }
}
